Introduction

You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing in the list.

Approach 1

Get the sum of numbers
```
total = n*(n+1)/2
```
Subtract all the numbers from sum and you will get the missing number.



In [1]:

    
data = [1, 2, 3, 4, 5, 6, 8]



In [2]:

    
def find_missing_number(data):
    ans = ((len(data) + 1) * (len(data) + 2)) / 2
    for x in data:
        ans -= x
    return ans



In [3]:

    
print find_missing_number(data)

Approach 2

1) XOR all the array elements, let the result of XOR be X1.

2) XOR all numbers from 1 to n, let XOR be X2.

3) XOR of X1 and X2 gives the missing number.



In [4]:

    
def find_missing_number_xor(data):
    a = data[0]
    for x in data[1:]:
        a ^= x
    b = 1
    for i in xrange(2, len(data) + 2):
        b ^= i
    return a ^ b



In [5]:

    
print find_missing_number_xor(data)

References

http://www.geeksforgeeks.org/find-the-missing-number/
http://practice.geeksforgeeks.org/problems/missing-number-in-array/0